import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
class Solution {
    //解法1:递归
    public List<Integer> postorderTraversal(TreeNode root) {
        //创建数组列表存储节点
        List<Integer> list = new ArrayList();
        //树为空则返回空列表
        if (root == null) return list;
        //左
        list.addAll(postorderTraversal(root.left));
        //右
        list.addAll(postorderTraversal(root.right));
        //根
        list.add(root.val);
        return list;
    }
    //解法2:迭代
    public List<Integer> postorderTraversal2(TreeNode root) {
        //创建数组列表存储节点
        List<Integer> list = new ArrayList();
        //树为空则返回空列表
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack();
        //记录当前节点
        TreeNode node = root;
        //记录上一个节点
        TreeNode prev = null;
        //遍历树
        while (node != null || !stack.isEmpty()) {
            //左侧节点依次入栈
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            //node指向最左侧节点
            node = stack.pop();
            //若没有右孩子或者右孩子为上一个已存储的节点,则添加列表,并更新 prev,重置 node为 null
            if (node.right == null || node.right == prev) {
                list.add(node.val);
                prev = node;
                node = null;
            } else {//若存在右孩子,则将node节点重新入栈,并向右孩子移动
                stack.push(node);
                node = node.right;
            }
        }
        return list;
    }
}